#include "main/utils.h"
#include "lib/binary_tree.h"
using namespace std;

void maxSumCore(BinaryTreeNode* root, int &path, int &max_sum) {
  if (!root) {
    return;
  }
  int left_path = INT_MIN, right_path = INT_MIN;
  int left_max_sum = INT_MIN, right_max_sum = INT_MIN;
  maxSumCore(root->left, left_path, left_max_sum);
  maxSumCore(root->right, right_path, right_max_sum);
  left_path = left_path > 0 ? left_path : 0;
  right_path = right_path > 0 ? right_path : 0;

  int cur_max = left_path + root->value + right_path;
  cur_max = cur_max > left_max_sum ? cur_max : left_max_sum;
  cur_max = cur_max > right_max_sum ? cur_max : right_max_sum;

  if (left_path > right_path) {
    path = left_path + root->value;
  } else {
    path = right_path + root->value;
  }
}

int maxSum(BinaryTreeNode* root) {
  int path = 0;
  int max_sum = INT_MIN;
  maxSumCore(root, path, max_sum);
  return max_sum;
}

int main() {
  vector<int> vec = {-9, 20, 4, 15, 7, 0, 0, -3};
  BinaryTreeNode* root = CreateBinaryTree(vec);
  int ret = maxSum(root);
  cout << ret << endl;

  return 0;
}
